Probleme de informatica - enunturi si rezolvari

Probleme de informatică

Clasa a IX-a

Elementele de bază C++ (46)

Subprograme predefinite (1)

Fişiere text (2)

Algoritmi elementari (111)

Tablouri unidimensionale (83)

Tablouri bidimensionale (64)

Probleme diverse (13)

Clasa a X-a

Subprograme (funcții) (87)

Şiruri de caractere (50)

Tipul înregistrare (26)

Recursivitate (57)

Alocarea dinamică a memoriei (2)

Liste înlănţuite (25)

Algoritmul lui Lee (1)

Clasa a XI-a

Metoda "Divide et impera" (12)

Metoda Backtracking (86)

Metoda Greedy (6)

Programare dinamică (18)

Grafuri neorientate (40)

Grafuri orientate (38)

Clasa a XII-a

Elemente de bază C# (32)

POO în C# (14)

Programare vizuală în C# (19)

Examen de bacalaureat

Competențe digitale

Examen de atestat

Admitere UBB (18)

Grafuri neorientate

#884. [2020-01-20 - 13:23:49]
Se dă un graf neorientat cu n (n<=100) vârfuri si m muchii prin lista muchiilor. Afisați toate subgrafurile pe care le are. Fiecare subgraf va fi afișat astfel:
- vârfurile lui
- matricea de adiacență
Exemplu:
graf.in
3 2
1 2
1 3
graf.out
Varfurile subgrafului: 1
Matricea de adiacenta:
0 0 0
0 0 0
0 0 0
Varfurile subgrafului: 1 2
Matricea de adiacenta:
0 1 0
1 0 0
0 0 0
Varfurile subgrafului: 1 2 3
Matricea de adiacenta:
0 1 1
1 0 0
1 0 0
Varfurile subgrafului: 1 3
Matricea de adiacenta:
0 0 1
0 0 0
1 0 0
Varfurile subgrafului: 2
Matricea de adiacenta:
0 0 0
0 0 0
0 0 0
Varfurile subgrafului: 2 3
Matricea de adiacenta:
0 0 0
0 0 0
0 0 0
Varfurile subgrafului: 3
Matricea de adiacenta:
0 0 0
0 0 0
0 0 0

#883. [2020-01-20 - 11:23:43]
Se dau două grafuri neorientate G1 și G2 cu n (n<=100) vârfuri și m1, respectiv m2 muchii prin listele muchiilor, în două fișiere graf1.in, respectiv graf2.in. Verificați dacă unul dintre ele este graf parțial al celuilalt. Se va preciza dacă G1 este graf parțial al lui G2, dacă G2 este graf parțial al lui G1 sau NU dacă niciunul dintre ele este graf parțial al celuilalt.
Exemplu:
graf1.in
5 2
1 4
1 3
graf2.in
5 5
1 4
1 3
3 5
4 5
2 5
graf.out
G1 este graf partial al lui G2

#882. [2020-01-20 - 10:45:58]
Se dă un graf neorientat cu n (n<=100) vârfuri si m muchii prin lista muchiilor. Afisați toate grafurile parțiale pe care le are. Fiecare graf parțial va fi afișat astfel:
- numărul lui de ordine (al câtelea a fost generat)
- lista munchiilor lui
- matricea de adiacență
Exemplu:
graf.in
4 2
1 4
1 3
graf.out
Graful partial numarul 1:
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
Graful partial numarul 2:
1 4
0 0 0 1
0 0 0 0
0 0 0 0
1 0 0 0
Graful partial numarul 3:
1 4
1 3
0 0 1 1
0 0 0 0
1 0 0 0
1 0 0 0
Graful partial numarul 4:
1 3
0 0 1 0
0 0 0 0
1 0 0 0
0 0 0 0

#820. [2017-01-25 - 08:55:11]
Din fisierul graf.in se citesc de pe prima linie numerele naturale n si l (l,n<=20) reprezentand numarul de varfuri ale unui graf complet si respectiv lungimea unui ciclu.
Afisati in fisierul graf.out, in ordine lexicografica, toate ciclurile elementare de lungime l ale grafului complet cu n varfuri.
Exemplu:
graf.in
5 3
graf.out
1 2 3 1
1 2 4 1
1 2 5 1
1 3 2 1
1 3 4 1
1 3 5 1
1 4 2 1
...
5 4 3 5

#819. [2017-01-25 - 08:41:50]
Din fisierul graf.in se citesc de pe prima linie numerele naturale n si m (n<=20) reprezentand numarul de varfuri si respectiv numarul de muchii ale unui graf neorientat. De pe urmatoarele m linii se citesc muchiile grafului, iar de pe ultima linie se citesc 3 numere naturale x,y,l.
Afisati in fisierul graf.out toate lanturile elementare de lungime l care au pe x ca extremitate initiala si pe y ca extremitate finala.
Exemplu:
graf.in
6 9
1 2
1 3
2 3
4 5
3 5
3 6
4 6
1 6
5 6
1 6 3
graf.out
1 2 3 6
1 3 5 6

#552. [2014-02-17 - 00:01:11]
Se sa un graf neorientat cu n varfuri si m muchii, fara varfuri izolate.
Sa se determine daca este eulerian si in caz afirmativ sa se afiseze un ciclu eulerian.
Pentru determinarea ciclului eulerian nu se va folosi metoda backtracking.
date.in:
6 10
1 2
1 6
2 3
2 5
2 6
3 4
3 5
3 6
4 5
5 6
date.out:
este eulerian
1 2 3 5 6 2 5 4 3 6 1

#506. [2013-11-13 - 19:34:59]
Se da un graf neorientat cu n varfuri si m muchii. Afisati grupurile de muchii incidente.
Exemplu
n=5 , m=4
muchiile:
[1,2]
[1,3]
[1,4]
[3,4]
grupurile de muchii incidente sunt
[1,2] [1,3] [1,4]
[1,3] [3,4]
[1,4] [3,4]

#472. [2013-05-17 - 12:35:48]
Se da un graf neorientat cu n varfuri si m muchii prin lista muchiilor. Afisati numarul minim de muchii care trebuie adaugate in graf pentru ca acesta sa fie conex si muchiile care trebuie adaugate.
Exemplu:
date.in
12 11
1 2
1 3
1 4
2 8
3 6
3 7
4 6
4 5
7 10
6 10
12 11
date.out
2
1 9
9 11
(muchiile nu sunt unice!)

#444. [2013-03-29 - 08:38:34]
Harta rutiera a unei tari este formata din n orase si m sosele intre 2 orase, fiecare sosea fiind caractezizata prin distanta in kilometri (numar natural).
Trei prieteni se gasesc in 3 orase distincte x, y, z si isi propun sa se intalneasce intr-un oras t.
Calculati si afisati distanta minima pe care o parcurge fiecare prieten din orasul de pornire pana in orasul t de destinatie.
Afisati cele trei orase de plecare in ordinea in care cei trei prieteni ajung in orasul t.
Exemplu:
date.in
12 19 (n,m)
1 2 20 (oras 1, oras 2, distanta)
1 3 35
1 7 20
2 4 30
3 4 40
3 6 40
3 8 80
4 5 25
5 6 5
6 8 30
6 9 10
7 8 15
7 11 100
8 9 40
8 10 30
8 11 35
9 10 30
10 12 25
11 12 10
1 5 3 12 (x, y, z, t)
date.out
Distantele parcurse de cei trei prieteni:
80 70 105
Orasele de plecare in ordinea in care ajung cei trei prieteni:
5 1 3

#441. [2013-03-21 - 08:21:55]
Se citeste un graf neorientat cu n noduri si m muchii dat prin vectorul muchiilor.
- Construiti matricea lanturilor folosind algoritmul Roy-Warshall.
- Folosind matricea lanturilor afisati componentele conexe.
Exemplu:
date.in
7 4
1 2
1 3
2 5
6 7
date.out
1 2 3 5
4
6 7

#425. [2013-02-18 - 00:37:56]
Se da un graf neorientat cu n noduri si m muchii precizat prin lista muchiilor. Calculati distantele minime dintre oricare doua noduri ale grafului si afisati distantele intr-o matrice A (nXn) in care fiecare element A[x][y] este egal cu distanta minima de la varful x la varful y. Distanta minima dintre doua varfuri este egala cu lungimea celui mai scurt lant care are cele doua noduri ca extremitati. Se va folosi parcurgerea in latime.
Exemplu:
date.in
8 9
1 2
1 4
2 3
3 4
3 5
5 6
7 8
4 6
date.out
0 1 2 1 3 2 # #
1 0 1 2 2 3 # #
2 1 0 1 1 2 # #
1 2 1 0 2 1 # #
3 2 1 2 0 1 # #
2 3 2 1 1 0 # #
# # # # # # 0 1
# # # # # # 1 0
(# semnaleaza faptul ca nu exista lant intre doua varfuri)

#424. [2013-02-18 - 00:29:08]
Se da un graf neorientat cu n varfuri si m muchii. Determinati numarul minim de culori cu care se pot colora varfurile grafului astfel incat oricare doua varfuri adiacente sa aiba culori diferite. Numerotand apoi culorile necesare, realizati o colorare a varfurilor grafului dat si afisati pentru fiecare culoare nodurile care se coloreaza cu ea.
Exemplu:
date.in
9 13
1 2
1 4
2 3
3 4
3 5
5 6
7 8
4 6
7 9
8 9
1 3
2 4
date.out
4
culoarea 1: 1 5 7
culoarea 2: 2 6 8
culoarea 3: 3 9
culoarea 4: 4

#423. [2013-02-18 - 00:23:31]
Se da un graf neorientat cu n varfuri si m muchii prin lista muchilor si un varf k. Afisati toate ciclurile elementare care au ca extremitate initiala si finala varful k.
Exemplu:
date.in
8 10 1
1 2
1 4
2 3
3 4
3 5
5 6
7 8
4 6
1 3
2 4
date.out
1 2 3 1
1 2 3 4 1
1 2 3 5 6 4 1
1 2 4 1
1 2 4 3 1
1 2 4 6 5 3 1
1 3 2 1
1 3 2 4 1
1 3 4 1
1 3 4 2 1
1 3 5 6 4 1
1 3 5 6 4 2 1
1 4 2 1
1 4 2 3 1
1 4 3 1
1 4 3 2 1
1 4 6 5 3 1
1 4 6 5 3 2 1

#422. [2013-02-18 - 00:20:04]
Se da un graf neorientat cu n varfuri si m muchii prin lista muchilor. Construiti matricea lanturilor folosind parcurgerea in adancime.
Exemplu:
date.in
8 9
1 2
1 4
2 3
3 4
3 5
5 6
7 8
4 6
date.out
0 1 1 1 1 1 0 0
1 0 1 1 1 1 0 0
1 1 0 1 1 1 0 0
1 1 1 0 1 1 0 0
1 1 1 1 0 1 0 0
1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0

#420. [2013-02-10 - 09:00:14]
Se da un graf neorientat conex cu n varfuri si m muchii. Eliminati un numar minim de muchii din graf astfel incat acesta sa nu mai contina nici un ciclu.
Se vor afisa muchiile eliminate si matricea de adiacenta a grafului partial obtinut astfel.
Exemplu:
date.in
4 6
1 2
1 3
1 4
2 3
2 4
3 4
date.out
[2,3]
[2,4]
[3,4]
0111
1000
1000
1000

#419. [2013-02-06 - 10:06:25]
Se da un graf neorientat conex cu n varfuri si m muchii. Determinati numarul minim de culori cu care se pot colora varfurile grafului astfel incat oricare doua varfuri adiacente sa aiba culori diferite.
Exemplu:
pentru graful cu 6 varfuri si 11 muchii dat prin vectorul muchiilor
1 2
1 3
1 4
2 3
3 4
3 5
3 6
4 7
5 6
6 7
2 4
numarul minim de culori este 4

#418. [2013-01-31 - 08:31:31]
Se da un graf neorientat cu n varfuri si m muchii prin vectorul muchiilor. Stabiliti daca graful este hamiltonian.

#417. [2013-01-24 - 13:32:28]
Se da un graf neorientat cu n noduri si m muchii precizat prin lista muchiilor. Se citesc apoi 2 varfuri x si y.
Afisati toate lanturile elementare care au ca extremitate initiala varful x si extremitate finala varful y.
date.in:
8 10
1 2
1 3
2 3
2 8
3 4
3 7
4 5
5 6
6 7
7 8
8 4
date.out:
8 2 1 3 4
8 2 1 3 7 6 5 4
8 2 3 4
8 2 3 7 6 5 4
8 7 3 4
8 7 6 5 4

#416. [2013-01-24 - 12:57:53]
Se da un graf neorientat cu n noduri si m muchii precizat prin lista muchiilor.
Determinati daca graful dat contine cel putin un ciclu.

#415. [2013-01-23 - 13:31:33]
Se da un graf neorientat cu n noduri si m muchii precizat prin lista muchiilor. Calculati distantele minime de la un nod citit s la toate celelalte noduri ale grafului. Distanta minima dintre doua varfuri este egala cu lungimea celui mai scurt lant care are cele doua noduri ca extremitati.
date.in:
8 12
1 2
1 3
2 4
2 5
3 4
4 5
4 6
4 8
6 7
7 8
3 6
5 6
2
date.out:
2->1:1
2->2:0
2->3:2
2->4:1
2->5:1
2->6:2
2->7:3
2->8:2

#413. [2013-01-17 - 12:35:28]
Se da un numar n si n valori intregi. Determinati daca cele n valori pot reprezenta gradele varfurilor unui graf neorientat cu n varfuri.
Exemple:
n=5
1 3 1 2 1 - da
1 5 1 2 1 - nu
1 4 1 2 1 - nu

#412. [2013-01-17 - 10:23:58]
Se citeste un numar natural n nenul. Construiti toate grafurile neorientate cu n varfuri.
Fiecare graf se va afisa atat ca matrice de adiacenta si prin vectorul muchiilor.
Doua grafuri sunt diferite daca au matricile de adiacenta diferite.

#411. [2013-01-17 - 09:21:12]
Se da un graf neorientat cu n varfuri si m muchii citit prin lista muchiilor.
a) Calculati si afisati gradul fiecarui varf.
b) Numarati cate varfuri terminale are graful.
c) Afisati varfurile care au grad maxim.
Exemplu:
date.in
5 6
1 2
1 4
1 5
2 4
3 5
4 5
date.out
vectorul gradelor:
3 2 1 3 3
numarul de noduri terminale:
1
nodurile cu grad maxim:
1 4 5

#410. [2013-01-16 - 11:43:08]
Memorarea grafurilor neorientate (fara STL).

#377. [2012-10-25 - 15:19:38]
Se da un graf conex cu n varfuri si m muchii prin vectorul muchiilor.
Stabiliti daca graful este bipartit, iar daca este atunci afisati cele doua multimi in care se poate imparti multimea varfurilor.
Exemplu:
date.in
4 4
1 2
2 3
3 4
4 1
date.out
da
1 3
2 4

#376. [2012-10-25 - 14:21:12]
Depth first cu listele vecinilor.
Ex:
date.in:
7 8
1 2
1 3
1 4
3 5
4 5
4 7
5 6
5 7
1
date.out: 1 2 3 5 4 7 6

#370. [2012-10-18 - 15:23:16]
Breadth first cu listele vecinilor.
Ex:
date.in:
7 8
1 2
1 3
1 4
3 5
4 5
4 7
5 6
5 7
1
date.out: 1 2 3 4 5 7 6

#365. [2012-10-11 - 14:38:31]
Memorarea grafurilor neorientate.

#315. [2010-12-15 - 11:04:36]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor.
Sa se afiseze matricea distantelor minime pentru distantele intre oricare 2 varfuri din graf. Daca nu exista lant intre doua varfuri atunci se va afisa caracterul #.
Se va folosi algoritmul Roy-Floyd.
Exemplu:
Fisierul de intrare:
12 13
1 2
1 3
1 4
2 8
3 6
3 7
4 6
4 5
8 9
7 9
7 10
6 10
12 11
Fisierul de iesire:
0 1 1 1 2 2 2 2 3 3 # #
1 0 2 2 3 3 3 1 2 4 # #
1 2 0 2 3 1 1 3 2 2 # #
1 2 2 0 1 1 3 3 4 2 # #
2 3 3 1 0 2 4 4 5 3 # #
2 3 1 1 2 0 2 4 3 1 # #
2 3 1 3 4 2 0 2 1 1 # #
2 1 3 3 4 4 2 0 1 3 # #
3 2 2 4 5 3 1 1 0 2 # #
3 4 2 2 3 1 1 3 2 0 # #
# # # # # # # # # # 0 1
# # # # # # # # # # 1 0

#314. [2010-12-15 - 11:01:10]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor si apoi un varf k.
Sa se afiseze pe linii separate distantele minime de la varful k la celelalte varfuri ale grafului si lanturile de lungime minima corespunzatoare acestor distante. Distanta de la un varf la altul se considera a fi numarul de muchii din cel mai scurt lant care uneste cele doua noduri.
Se va folosi un algoritm de tip breadth first.
Exemplu:
Fisierul de intrare:
12 13
1 2
1 3
1 4
2 8
3 6
3 7
4 6
4 5
8 9
7 9
7 10
6 10
12 11
8
Fisierul de iesire:
1 2 8 2 1
2 1 8 2
3 3 8 2 1 3
4 3 8 2 1 4
5 4 8 2 1 4 5
6 4 8 2 1 3 6
7 2 8 9 7
8 0 8
9 1 8 9
10 3 8 9 7 10
11 -
12 -

#313. [2010-12-15 - 10:58:20]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor si apoi un varf k.
Sa se afiseze pe linii separate distantele minime de la varful k la celelalte varfuri ale grafului. Distanta de la un varf la altul se considera a fi numarul de muchii din cel mai scurt lant care uneste cele doua noduri.
Se va folosi un algoritm de tip breadth first.
Exemplu:
Fisierul de intrare:
12 13
1 2
1 3
1 4
2 8
3 6
3 7
4 6
4 5
8 9
7 9
7 10
6 10
12 11
8
Fisierul de iesire:
1 2
2 1
3 3
4 3
5 4
6 4
7 2
8 0
9 1
10 3
11 -
12 -

#312. [2010-12-15 - 10:47:45]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze pe linii separate componentele sale conexe. Se va folosi un algoritm de tip depth first.
Exemplu:
Fisierul de intrare:
12 13
1 2
1 3
1 4
2 8
3 6
3 7
4 6
4 5
8 9
7 9
7 10
6 10
12 11
Fisierul de iesire:
1 2 8 9 7 3 6 4 5 10
11 12

#285. [2010-11-24 - 17:32:49]
Se citeste un graf neorientat precizat prin vectorul muchiilor dintr-un fisier text in care pe prima linie avem numarul de varfuri si cel de muchii si apoi muchiile.
a) Construiti si afisati matricea de adiacenta a grafului precedata de numarul de varfuri.
b) Afisati listele de adiacenta prin care se poate reprezenta graful.
c) Afisati muchille grafului.
d) Din fisierul de intrare se mai citeste un varf k. Calculati si afisati gradul varfului k.
Pentru graful dat astfel:
6 6
1 3
1 5
1 2
2 3
3 4
4 5
3
Se vor afisa urmatoarele:
6
0 1 1 0 1 0
1 0 1 0 0 0
1 1 0 1 0 0
0 0 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
1 -> 2 3 5
2 -> 1 3
3 -> 1 2 4
4 -> 3 5
5 -> 1 4
6 ->
1,2
1,3
1,5
2,3
3,4
4,5
3

#47. [2009-03-19 - 11:39:59]
Se citeste un graf neorientat cu n noduri si m muchii dat prin vectorul muchiilor si se citeste apoi un numar k mai mic decat n. Sa se afiseze toate ciclurile elementare de lungime k din graf.

#34. [2009-03-09 - 18:47:25]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze toate ciclurile euleriene pe care le are graful.

#33. [2009-03-09 - 16:24:04]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se determine daca este graf eulerian.

#32. [2009-03-09 - 16:15:26]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze cea mai mare dintre componentele sale conexe.
Ex: Pentru graful alaturat se va afisa componenta conexa 1 2 4 5

#31. [2009-03-09 - 16:07:56]
Se da un graf neorientat cu n varfuri si m muchii, citit prin vectorul muchiilor. Sa se afiseze pe linii separate componentele sale conexe.
Ex: Pentru graful alaturat se vor afisa urmatoarele componente conexe:
1 2 4 5
3 7
6

#22. [2009-03-08 - 00:02:37]
Se citesc 2 grafuri neorientate, unul cu n noduri si m muchii, iar celalalt cu k varfuri si l muchii, ambele date prin vectorul muchiilor. Sa se determine daca al doilea graf este subgraf al primului.

#9. [2009-03-07 - 21:33:34]
Matricea lanturilor - algoritmul Roy-Warshall
Se citeste un graf neorientat cu n noduri si m muchii dat prin vectorul muchiilor. Sa se construiasca o matricea existentei lanturilor(a[i][j] este 1 daca exista lant de la i la j si 0 in caz contrar).
Ex: Pentru graful din imagine se obtine matricea lanturilor urmatoare:
0 0 1 1 1 1
0 0 0 0 0 0
1 0 0 1 1 1
1 0 1 0 1 1
1 0 1 1 0 1
1 0 1 1 1 0

27 apr 2024

Site-ul conține 884 de probleme rezolvate

Copyright © 2009-2018 Muresan Vasile Ciprian